// https://www.lintcode.com/problem/find-minimum-in-rotated-sorted-array/

public class Solution {
    /**
     * @param nums: a rotated sorted array
     * @return: the minimum number in the array
     */
    public int findMin(int[] nums) {
        // write your code here
        if (nums.length == 1) {
          return nums[0];
        }
        int start = 1;
        int end = nums.length - 1;
        while (start < end) {
          int mid = (start + end) / 2;
          if ((nums[mid] < nums[mid - 1]) && (nums[mid] < nums[mid + 1])) {
            return nums[mid];
          } else if (nums[mid] > nums[0]) {
            ++start;
          } else {
            --end;
          }
        }
        return Math.min(nums[0], nums[nums.length - 1]);
    }
}